package com.example.javamaday.leetcode;

import com.example.javamaday.leetcode.base.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ConcurrentLinkedQueue;

public class LeetCodeTest0102 {

    public static void main(String[] args) {

    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        boolean isRevert = false;
        ConcurrentLinkedQueue<TreeNode> nodes = new ConcurrentLinkedQueue<>();
        ConcurrentLinkedQueue<TreeNode> helperNodes = new ConcurrentLinkedQueue<>();
        List<List<Integer>> result = new ArrayList<>();
        nodes.add(root);
        while (!nodes.isEmpty() || !helperNodes.isEmpty()) {
            if (!isRevert) {
                ArrayList<Integer> list = new ArrayList<>();
                while (!nodes.isEmpty()) {
                    TreeNode n = nodes.poll();
                    list.add(n.val);
                    if (n.left != null) {
                        helperNodes.add(n.left);
                    }
                    if (n.right != null) {
                        helperNodes.add(n.right);
                    }
                }
                result.add(list);
                isRevert = true;
            } else {
                ArrayList<Integer> list = new ArrayList<>();
                while (!helperNodes.isEmpty()) {
                    TreeNode n = helperNodes.poll();
                    list.add(n.val);
                    // 判断当前结点还有没有左子结点，如果有，则放到nodes中
                    if (n.left != null) {
                        nodes.add(n.left);
                    }
                    // 判断当前结点还有没有右子结点，如果有，则放到nodes中
                    if (n.right != null) {
                        nodes.add(n.right);
                    }
                }
                result.add(list);
                isRevert = false;
            }
        }
        return result;
    }
}
